1. Field of the Invention
The present invention relates, in general, to graphical user interfaces, and, more particularly, to software, systems and methods for display and selection of objects in three-dimensional graphical displays.
2. Relevant Background
Although computers and data communication networks have revolutionized the processes of exchanging information, they are primarily used to exchange one-dimensional or two-dimensional data. In other words, existing systems are efficient at communicating raw data such as text and numbers (i.e., one-dimensional data) and some formatted data such as graphs and text on a formatted page (i.e., two-dimensional data). However, three-dimensional data used in computer aided design (CAD) and computer aided manufacturing (CAM) tools tend to be handled by more advanced machines.
It is important to distinguish between three-dimensional display devices and three-dimensional graphical user interfaces. Many techniques for rendering images that appear to be three-dimensional are known. These systems use perspective drawing techniques to display three-dimensional images, but interact with users in a conventional two-dimensional fashion. A graphical user interface, in contrast, requires that a user be able to select and interact with three-dimensional graphical objects, not just view them.
Although a markup language called virtual reality markup language (VRML) is being developed for three-dimensional rendering, these efforts are directed to rendering three-dimensional graphics and not to systems and methods that enable interaction with three-dimensional graphical objects. Alternatively, active content such as Java and ActiveX are used to create three-dimensional objects with programmatically defined behavior. However, such systems rely on complex mathematical computations to distinguish objects within a particular window and so have not been widely accepted to implement three-dimensional graphical user interfaces.
Three-dimensional graphical displays are implemented on two-dimensional display devices where the image is rendered and drawn in a manner that visually conveys the three-dimensional relationships between objects. Using an x-y reference to indicate the horizontal and vertical axes of the display and a z axis to indicate distance from the viewer, at any given x-y location, any number of objects may exist in different z planes. Only one of the objects, however, is closest to the viewer.
Most graphical user interface (GUI) software for selecting displayed objects allows a user to identify a particular x-y location (or range of locations) using a mouse, keyboard, joystick, pen/tablet, or other user input device that allow a user to manipulate the position of a cursor on a display. In some instances the x-y location information is communicated from the GUI processes to other processes that provide information about the object(s) in the vicinity of a cursor. For example, information about a displayed object or a related help dialog may be displayed while a cursor hovers or floats above a particular x-y location. A user may select the object at that x-y location by activating a control on the user interface device. With two-dimensional data only a single object will exist at any selected x-y location.
However, a significant challenge for 3-D graphical user interfaces involves selection of the object closest to the viewer's perspective from amongst the layered objects that exist at a particular x-y location. The system must first determine which of the several objects at a particular x-y location is the “nearest” to the user. GUI processes found in most operating systems communicate only x-y location information to external processes. In most cases, the GUI processes may communicate color information as well. Hence, the information provided by the GUI processes is ambiguous with respect to which object is the closest to the user in a 3-D display.
In three-dimensional graphical software, processes and data structures exist that maintain information about the object's placement in x, y and z dimensions. A “z-buffer” refers to a software or hardware data structure that holds depth information for each given x-y location to manage which screen elements can be viewed and which are hidden behind other objects. A typical configuration of a z-buffer comprises a number of bits of memory associated with each display pixel where the bit value indicates the distance in the z-axis of the displayed pixel. A rendering algorithm can then draw only pixels with a z-buffer value indicating a closer position to the viewer (e.g., the pixels with the largest or smallest z-buffer value) at each x-y location. The z-buffer may be maintained by application software, or by specialized graphic subsystem such as a graphics accelerator card in a personal computer. These subsystems tend to be memory intensive to provide multiple bits of resolution in the z-axis for each pixel of the display.
When an application creates a 3D graphical object, a set of points is used to represent a shape. The points are then connected by lines to form a mesh or wireframe. The wireframe defines a set of polygons that represent surfaces of the graphical object. Once the polygons have been created, the application software can then shade the individual polygons to create the appearance of a solid object, or apply texture to the object. The greater the number of points used to define the shape, the greater the resolution that the object can be displayed.
In a complex scene comprising multiple objects, the application must create and track many objects and surfaces that may not be visible in a particular scene. Each time the display is drawn, application software selects the graphical objects having surfaces that will be visible on the screen at each pixel of the display. For each point in the scene, a surface depth ordering is performed by computing a z-distance for each object from a particular vantage point or “camera” view. The z-distance is typically expressed in some units of measure defined by the application itself such as “meters” or “feet” or an arbitrary scale used by the application. Intersections of multiple objects at each x-y location are detected, and one object to be displayed is selected for each pixel based on the z-distance (ignoring, for the moment, transparent objects).
Some of the rendering tasks may be handed off to a graphics subsystem, in which case the z-distance may be converted into a z-buffer value expressed in arbitrary units understood by the graphics subsystem. Information is communicated from the graphic subsystem to a two-dimensional display buffer in the form of x-y coordinates and color data for that coordinate. Significantly, the display buffer, also called a “frame buffer” has no knowledge of the objects it is displaying or whether they are one-, two-, or three-dimensional.
To select a displayed object using a GUI a given x-y location is selected, which is used by the graphics subsystem to determine a “pick ray” extending from a virtual eye point used for rendering and the point at the x-y location selected. This ray is geometrically intersected with all polygons of all objects, which may be up to many hundreds of thousands of polygons. The polygon with the nearest intersection to the viewer belongs to the selected object. This process is computationally expensive process.
Moreover, in client-server systems where the some or all of the processing must occur on a server that is physically distant from the display device, object selection processes are slow. Some improvements have been realized in the display of 3D graphical objects, but improvements that allow selection and user interaction with 3D graphical user interfaces has lagged. In essence, these systems portray a user interface that appears three-dimensional, but in practice is two-dimensional when in terms of object selection. Moreover, many proposed systems require specialized browser software or plug-ins to operate. As a result, implementation of lightweight computing devices to serve as three-dimensional graphical user interfaces has been impractical.